//给定正整数 n ，我们按任何顺序（包括原始顺序）将数字重新排序，注意其前导数字不能为零。 
//
// 如果我们可以通过上述方式得到 2 的幂，返回 true；否则，返回 false。 
//
// 
//
// 
// 
//
// 示例 1： 
//
// 
//输入：n = 1
//输出：true
// 
//
// 示例 2： 
//
// 
//输入：n = 10
//输出：false
// 
//
// 
//
// 提示： 
//
// 
// 1 <= n <= 10⁹ 
// 
//
// Related Topics 哈希表 数学 计数 枚举 排序 👍 203 👎 0


package LeetCode.editor.cn;

import java.util.*;

/**
 * @author ldltd
 * @date 2025-08-10 23:03:16
 * @description 869.重新排序得到 2 的幂
 */
public class ReorderedPowerOf2{
	 public static void main(String[] args) {
	 	 //测试代码
	 	 ReorderedPowerOf2 fun=new ReorderedPowerOf2();
	 	 Solution solution = fun.new Solution();
		 System.out.println(String.valueOf(Math.pow(2,30)));
	 }
	 
//力扣代码
//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
		 //先将 n 转换为字符串，统计每个数字的出现次数
	 // 然后生成所有可能的数字，检查是否为 2 的幂
	//	 由于 n 的范围是 1 到 10^9，所以最多有 10 位数字
	//    2的30次方是1,073,741,824
	//	  2 的幂的范围是 1 到 2^30，所以我们只需要检查 31 个可能的数字
    public boolean reorderedPowerOf21(int n) {
        int x=n;
		Map<Integer,Integer> map=new HashMap<>();
		while (x>0){
			int digit=x%10;
			map.put(digit,map.getOrDefault(digit,0)+1);
			x/=10;
		}

		for (int i=0;i<=30;i++){
			int powerOf2=(int)Math.pow(2,i);
			Map<Integer,Integer> powerMap=new HashMap<>();
			int temp=powerOf2;
			while (temp>0){
				int digit=temp%10;
				powerMap.put(digit,powerMap.getOrDefault(digit,0)+1);
				temp/=10;
			}
			if (map.equals(powerMap)){
				return true;
			}
		}
		return false;
    }

	private  final Set<String> powTwoSortedStrSet = new HashSet<>();
	// 预计算所有 2 的幂的数字字符串
	 {
		final int MAX_N = 1_000_000_000;
		for (int i = 1; i < MAX_N; i <<= 1) {
			String s = intToSortedStr(i);
			powTwoSortedStrSet.add(s);
		}
	}

	private  String intToSortedStr(int n) {
		char[] s = String.valueOf(n).toCharArray();
		Arrays.sort(s);
		return new String(s);
	}
	// 该方法将整数转换为字符串并排序，检查和预计算的 2 的幂的字符串集合是否匹配
	// 一个字符串能否通过重新排列得到 2 的幂
	// 约等于该数字的字符串和2^k是字母异位词
	public boolean reorderedPowerOf2(int n) {
		String s = intToSortedStr(n);
		return powTwoSortedStrSet.contains(s);
	}

}
//leetcode submit region end(Prohibit modification and deletion)

}
